The invention relates to methods and apparatus for evaluating software run-time schedulers and, more particularly, to quantifying the impact of software run-time schedulers on the performance of software applications running on embedded multimedia end-systems.
Embedded multimedia end-systems, such as, for example, personal digital assistants (PDAs), set-top boxes, and Internet terminals, often need to support multiple concurrent tasks such as, for example, audio, speech, video, graphics, and modem. While such end-systems typically have limited processing capability, they are being used to support increasingly sophisticated multimedia applications.
Multimedia applications typically impose real-time processing constraints. In other words, such applications have to finish processing within a certain time deadline. However, such applications can tolerate a small number of misses when the processing takes longer than the prescribed deadline. A multimedia application may have a performance constraint such as, for example, xe2x80x9cno more than 5% of deadlines may be missed.xe2x80x9d Such a constraint is referred to as a soft deadline constraint. End-systems typically support multimedia applications with soft deadlines through sophisticated software run-time schedulers.
One way a run-time scheduler supports multiple applications is through first-come first-serve (FCFS) scheduling, where each application gets its turn in order of arrival of the application. However, such a scheduling discipline may not allow the end-system to support applications with distinct deadlines. Consequently, there is a trend toward use of more sophisticated schedulers which allow priorities to be specified for applications. Earliest deadline first (EDF) and rate monotonic (RM) scheduling are examples of priority-based scheduling.
Given a particular architecture of an embedded system and a set of applications, it is unclear whether a particular run-time scheduler can support the multimedia applications adequately. There is no known method or apparatus which analytically computes the impact of different priority-based run-time scheduling policies on the performance of multimedia applications in terms of the soft deadline performance. Further, it is often necessary to control these schedulers in order to support the multimedia applications efficiently.
It is known that simulation may be used as a tool for predicting the performance of end-systems. However, simulation is inherently computation-intensive and, thus, time consuming, especially when thousands of runs are required in gathering statistics such as how often a deadline is missed. Alternatively, other conventional methods such as rate-monotonic analysis (RMA) can not be used when applications have soft deadlines or variability, as is the case with multimedia applications.
The invention provides methodology and apparatus for calculating the performance of one or more applications running on an end-system which has been configured with a particular run-time scheduling policy.
In one aspect of the invention, a method of evaluating an effect of a run-time scheduling policy on a performance of an end-system, having associated resources, running one or more applications, each application having one or more tasks and the tasks being mapped to the associated resources of the end-system, is disclosed. The method includes generating a state process having a state space representative of an evolution of computation associated with the end-system, the evolution being representative of task transitions with respect to the applications, available resources and the run-time scheduling policy. Then, given the state space generated with respect to, among other things, the specified run-time scheduling policy, the method includes computing performance metrics from the state process, the performance metrics being representative of the effect of the run-time scheduling policy on the performance of the one or more applications running on the end-system. The invention preferably calculates the performance in terms of the probability distribution of the processing delay of each application and a deadline miss probability. Such performance metrics may be used to influence the behavior of the run-time scheduler in the system in order to ensure that all applications get their due share of the end-system resources.
Advantageously, the methodology and apparatus of the invention can be used to control the run-time scheduler on the end-system so that it can provide adequate support to applications running on the end-system. In a preferred embodiment, the applications are multimedia applications and the end-system is an embedded end-system. The run-time scheduling policies may be priority-based, e.g., RM and EDF, or nonpriority-based, e.g., FCFS.